/**
 * 
 */
package string.passed2;

/**
 * @author xyyi
 *
 */
public class StrStr {

	/**
	Implement strStr().

	Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
	
	KMP Solution
	http://www.matrix67.com/blog/archives/115
	 */
	public String strStr(String str, String target) {

		if (target == null || target.isEmpty())
			return target;

		if (str == null || str.isEmpty())
			return null;

		int[] next = buildNext(target.toCharArray());
		int ti = -1;
		for (int si = 0; si < str.length(); si++) {
			while (ti >= 0 && target.charAt(ti + 1) != str.charAt(si))
				ti = next[ti];
			if (target.charAt(ti + 1) == str.charAt(si))
				ti++;
			if (ti == target.length() - 1)
				return str.substring(si - target.length() + 1);
		}

		return null;
	}

	// next[k] : if k + 1 is not match, the target start position
	private int[] buildNext(char[] str) {
		assert (str != null && str.length > 0);

		int[] next = new int[str.length];
		int pre = -1;
		next[0] = pre;
		for (int curr = 1; curr < next.length - 1; curr++) {
			while (pre >= 0 && str[pre + 1] != str[curr])
				pre = next[pre];
			if (str[pre + 1] == str[curr])
				pre++;
			next[curr] = pre;
		}

		return next;
	}

	boolean hasSubstring2(String str, String find) {
		assert(str != null && find != null);
		
		if (str.length() == 0 && find.length() == 0 ) {
			return true;
		}
		
		boolean result = false;
		for (int si = 0; si < str.length(); ++si) {
			if (si + find.length() > str.length()) {
				break;
			}
			boolean foundMatch = true;
			for (int fi = 0; fi < find.length(); ++fi) {
				if (str.charAt(si+fi) != find.charAt(fi)) {
					foundMatch = false;
					break;
				}
			}
			if (foundMatch) {
				result = true;
				break;
			}
		}
		
		return result;
	}

	boolean hasSubstring(String str, String find) {
		if (str == null && find == null)
			return true;
		
		if (str.length() == 0 && find.length() == 0)
			return true;
		
		boolean result = false;
		for (int i = 0; i < str.length(); ++i) {
			if (i + find.length() > str.length())
				break;
			
			int index = 0;
			while (index < find.length() && i + index < str.length()) {
				if (find.charAt(index) != str.charAt(i+index))
					break;
				index++;
			}
			if (index == find.length()) {
				result = true;
				break;
			}
		}
		
		return result;
	}
	
	
	
    public int strStr1(String haystack, String needle) {
        // if (haystack == null || haystack.isEmpty() || 
        //     needle == null || needle.isEmpty() || haystack.length() < needle.length()) {
        //     return -1;        
        // }
        if (haystack.equals(needle)) {
            return 0;
        }
        
        int result = -1;
        for (int si = 0, siSize = haystack.length() - needle.length() + 1; si < siSize; si++) {
        	String tmp = haystack.substring(si, si + needle.length());
            if (tmp.equals(needle)) {
                result = si;
                break;
            }
        }
        
        return result;
    }
	
	/**
	 * 
	 */
	public StrStr() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		StrStr ss = new StrStr();
		String str = "mississippi";
		String target = "issippi";
		int i = ss.strStr1(str, target);
		System.out.println(i);
		
		
//		StrStr ss = new StrStr();
//		String str = "abate";
//		String find = "bat";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		str = "beat";
//		find = "bat";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		str = "beat";
//		find = "";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		str = "";
//		find = "beat";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		str = "bat";
//		find = "beat";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		str = "bat";
//		find = "bat";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");
//		
//		
//		str = "";
//		find = "";
//		System.out.printf("\"%s\" is sub string of \"%s\": %s\n", find, str, ss.hasSubstring2(str,  find) ? "true" : "false");	

	}

}
